0109. 有序链表转换二叉搜索树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 快慢指针 + 递归

1. 📝 题目描述

• leetcode

给定一个单链表的头节点 head，其中的元素 按升序排序，将其转换为 平衡 二叉搜索树。

平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

---

示例 1：

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2：

输入: head = []
输出: []

---

提示：

• head 中的节点数在[0, 2 * 10^4] 范围内
• -10^5 <= Node.val <= 10^5

2. 🎯 s.1 - 快慢指针 + 递归

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* sortedListToBST(struct ListNode* head) {
    if (!head) return NULL;
    if (!head->next) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = head->val;
        node->left = node->right = NULL;
        return node;
    }

    // 快慢指针找中点
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = NULL;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = NULL;  // 断开左半段

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = slow->val;
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(slow->next);
    return root;
}

js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function (head) {
  if (!head) return null
  if (!head.next) return new TreeNode(head.val)

  // 快慢指针找中点，prev 记录中点前一个节点
  let slow = head,
    fast = head,
    prev = null
  while (fast && fast.next) {
    prev = slow
    slow = slow.next
    fast = fast.next.next
  }

  // 断开左半段
  prev.next = null

  const root = new TreeNode(slow.val)
  root.left = sortedListToBST(head)
  root.right = sortedListToBST(slow.next)
  return root
}

py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)

        # 快慢指针找中点
        slow, fast, prev = head, head, None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None  # 断开左半段

        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

• 时间复杂度：$O(n\log n)$，每层递归用快慢指针找中点需 $O(n)$，共 $O(\log n)$ 层
• 空间复杂度：$O(\log n)$，递归栈深度为平衡树高度

算法思路：

• 用快慢指针找链表中点作为当前子树的根节点，保证树高度平衡
• 断开中点前的链接，将链表分为左半段和右半段
• 递归地将左半段构建为左子树、右半段（中点之后）构建为右子树